package 二零年8月;

/**
 *  数字序列中的某一位数字
 *
 * 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
 *
 * 请写一个函数，求任意第n位对应的数字。
 *
 * 思路：
 * 0-9这样的一位数可以贡献长度1，这些数一共可以贡献10个长度；
 * 10-99这样的两位数可以贡献长度2，这些数一共可以贡献2 * 90 = 180个长度；
 * 100-999这样的三位数可以贡献长度3，这些数一共可以贡献3 * 900 = 2700个长度；
 * 以此类推八位数可以贡献长度8，这些数一共可以贡献90000000 * 8 = 720000000个长度
 *
 *  所以根据对应位数的长度与n匹配，确定n位在哪个范围中，然后遍历相应范围即可。
 */
public class S44 {
    private static int []sum={10, 190, 2890, 38890, 488890, 5888890, 68888890, 788888890}; // 0, 一位数，两位数，三位数……的累计数字的和

    public int findNthDigit(int n) {
        if(n<=9){
            return n;
        }
        int i=0;
        for(;i<sum.length && n>=sum[i];i++); // 循环找到n在sum中对应的范围
        int left=n-sum[i-1]; //n位于该范围的位置
        int index=left/(i+1);
        int offset=left % (i+1);
        String num=String.valueOf((int)Math.pow(10,i)+index);
        return num.charAt(offset)-'0';
    }
}
